package offer;

/**
 * @Author Elephas
 * @Date 2022/1/23
 **/
public class CanJump {
    static int sum = 0;
    public static void main(String[] args) {
        int[] TEST_01 = new int[]{6,6,6,6,6,6};
        final int[] TEST_02 = new int[]{2,3,1,1,4};
        new CanJump().canJump4(TEST_02);
        System.out.println(sum);
    }
    /*
        解法一：递归 + 动态规划求解，时间复杂度o(n),空间复杂度o(n)
     */
    public boolean canJump(int[] nums){
        if(nums.length == 1){
            if(nums[0] == 0) {
                return true;
            }
        }
        boolean dp[] = new boolean[nums.length - 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = false;
        }
        canJumpIterate(nums,nums.length - 1,dp);
        return dp[0];
    }
    public void canJumpIterate(int[] nums, int curTail,boolean[] dp){
        for (int i = curTail - 1; i > 0; i--) {
            if(!dp[i]){
                if(nums[i] + i >= curTail){
                    dp[i] = true;
                    canJumpIterate(nums,i,dp);
                }
            }else{
                break;
            }
        }
    }
    /*
        自底向上递归
     */
    public boolean canJump2(int[] nums){
        boolean[] dp = new boolean[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = false;
        }
        canJumpBottomToTopIterate(nums,0,dp);
        return dp[nums.length - 1];
    }
    public void canJumpBottomToTopIterate(int[] nums,int current,boolean[] dp){
        sum+=1;
        System.out.printf("call: %d\n",current);

        if(current >= nums.length){
            return;
        }
        if(dp[current]){
            return;
        }
        dp[current] = true;
        int curStep = nums[current];
        for (int i = 1; i <= curStep; i++) {
            if(current + i < nums.length && dp[current + i]){
                continue;
            }else if(current+i < nums.length){
                canJumpBottomToTopIterate(nums,current + i,dp);
            }
        }
    }
    /*
        题解：贪心法，有如下假设，若下标x可达，则下标0-x均可达，维护一个当前最远可达标记
     */
    public boolean canJump3(int[] nums){
        int furthest = 0;
        for (int i = 0; i < nums.length; i++) {
            if(i <= furthest) {
                if (nums[i] + i > furthest) {
                    furthest = nums[i] + i;
                }
            }else if(i > furthest || furthest >= nums.length - 1){
                break;
            }
        }
        return furthest >= (nums.length - 1);
    }

    /*
        将尾递归转化为迭代
     */
    public boolean canJump4(int nums[]){
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;

        for (int i = 0; i < dp.length; i++) {
            if(dp[i]){
                int step = nums[i];
                for (int j = 1; j <= step; j++) {
                    int jumpTarget = j+i;
                    if( jumpTarget < dp.length) {
                        dp[jumpTarget] = true;
                    }
                }
            }else{
                break;
            }
        }
        return dp[nums.length - 1];
    }
}